package com.ting.test.algorithms.大厂刷题班;

/**
 * 返回一个数组中选择的数字不能相邻的最大子序列累加和
 * <p>
 * 思路
 * 还是求最大子序列的累加和
 * <p>
 * 只是条件变为不能相邻
 * <p>
 * 求以i位置为结尾的子序列中，最大的累加和是多少
 */
public class 返回一个数组中选择的数字不能相邻的最大子序列累加和 {

    public static void main(String[] args) {
        int[] arr = new int[2];
        int sum = process(arr);
    }

    private static int process(int[] arr) {
        if (arr == null) {
            return 0;
        }
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = Math.max(arr[0], arr[1]);
        for (int i = 1; i < arr.length; i++) {
            // 有三种情况
            //1. 只要当前位置的元素
            //2. 从0到i不包含当前位置元素
            //3. 从0到i包含当前位置元素
            dp[i] = Math.max(arr[i], Math.max(dp[i - 1], arr[i] + dp[i - 2]));
        }
        return dp[arr.length - 1];
    }
}
